class TopVotedCandidate {

    private int[] persons;
    private int[] times;
    private int[][] preVotes;
    private int[] maxPersonVolte;
    private int min;
    private int max;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.persons = persons;
        this.times = times;
        init();
    }
    // 使用前缀和思想记录time时间前最高得票人
    private void init(){
        int length = persons.length;
        int personNum = 0;
        min = times[0];
        max = times[length-1];
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<length; i++){
            int person = persons[i];
            if(!set.contains(person)){
                personNum++;
                set.add(person);
            }
        }
        int[] perNums = new int[personNum];//记录每个候选人的选票
        maxPersonVolte = new int[2];//记录选票最多的候选人和票数
        preVotes = new int[length][3];//记录每个时间选票最多的候选人和票数
        for(int i=0; i<length; i++){
            perNums[persons[i]]++;
            if(maxPersonVolte[1]<=perNums[persons[i]]){
                maxPersonVolte[0] = persons[i];
                maxPersonVolte[1] = perNums[persons[i]];
            }
            preVotes[i][0] = times[i];
            preVotes[i][1] = maxPersonVolte[0];
            preVotes[i][2] = maxPersonVolte[1];
        }
    }
    
    public int q(int t) {
        if(t>max)return maxPersonVolte[0];
        if(t<min)return -1;
        int i = getMaxNum(t);
        return preVotes[i][1];
    }

    //二分查找时间t对应的times数组的时间
    private int getMaxNum(int t){
        int left = 0, right = times.length-1;
        while(left < right){
            int mid = (left+right+1)/2;
            if(times[mid]<=t){
                left = mid;
            }else{
                right = mid-1;
            }
        }
        return right;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */